package com.tencent50.easy;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhengTao
 * @version 1.0
 * @description:  只出现一次的数字 ,做出来不难，主要题目要求空间复杂度
 *你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
 * 1.异或方法
 * 交换律：a ^ b ^ c <=> a ^ c ^ b
 * 任何数于0异或为任何数 0 ^ n => n
 * 相同的数异或为0: n ^ n => 0
 * 2，list add和remove
 * @date 2022/7/24 15:10
 */
public class Demo11 {
    public static void main(String[] args) {
      int[] num={2,2,1};
        System.out.println(singleNumber1(num));
    }
    //异或运算
    public int singleNumber(int[] nums) {
          if(nums.length<=0){
              return 0;
          }
         int res=0;
         for (int num : nums) {
            res=res^num;
         }
        return res;
    }
    //list add和remove
    public static int singleNumber1(int[] nums) {
        List<Integer> num=new ArrayList<>();
        for (int i : nums) {
            if (num.contains(i)) {
                num.remove(i);
            }else {
                num.add(i);
            }
        }
        return num.get(0);
    }
}
